//什么是函数递归
//函数自己调用自己就是递归
//好处：只需要用少量的程序就可以描述出解题过程中所需要的多次重复计算，大大地减少了程序的代码量
//核心：大事化小

//通过一个例子，说明函数递归
//接收一个无符号的整型值，按照顺序输出它的每一位
//例如：输入123，输出1 2 3
#include <stdio.h>

void print(unsigned int n)
{
    //递归的两个必要条件：
    //1.存在限制条件，当满足这个条件时，递归将不再继续
    //2.每次递归调用之后越来越接近这个限制条件（也就是逼近条件）
    //限制条件与逼近条件缺一不可，缺少一个都会造成死递归，从而栈溢出

    //如果递归的层次太深，即使满足递归的两个必要条件，不会死递归，也会造成栈溢出
    //所以递归层次太深造成栈溢出的话，就尝试使用非递归的方式，或者使用静态对象代替非静态对象，均衡栈区和静态区的空间（不能100%解决问题）

    //这里的n>9就是限制条件，如果没有这个限制条件，将会陷入死递归
    //死递归的本质是栈溢出
    //C语言的内存分为栈区、堆区、静态区
    //而每次函数的调用都会向栈区申请空间
    //如果陷入死递归，就会无限的向栈区申请空间
    //而栈区的空间总是有限的，最后就会造成栈溢出(Stack overflow)
    if (n > 9)
    {
        //例如输入123
        //123大于9，将会进入这个if语句，执行print(n / 10)，进行"递"的操作，这里的n / 10就是越来越接近限制条件的关键
        //"递"就是将n / 10的结果（12）作为实参递给下一个print函数
        //下一个print函数将会继续同样的操作，将结果1作为实参传给下一个print函数
        //而1不满足n<9这个限制条件，将不会执行if语句的内容，会直接执行printf语句，输出1，然后这个函数会结束调用，进行"归"的操作
        //"归"就是按照"递"的反向顺序依次一层一层返回上一层函数，如果上一层函数还有没执行的语句，会在"归"的过程中执行
        //在这个函数中，就会执行printf语句，最后输出结果为1 2 3
        print(n / 10);
    }
    printf("%d ", n % 10);
}
int main()
{
    unsigned int num = 0;
    scanf("%u", &num);
    print(num);
    return 0;
}

//定义一个函数，输出字符串的长度
//一般方法：
#include <stdio.h>
#include <string.h>

int my_strlen(char* str) //用指针变量接收地址或者使用char arr[]都可以
{
    int count = 0; //找字符的次数，也就是记录字符长度；这里的count为临时变量
    while (*str != '\0') //对指针变量解引用，找到字符的内容，如果字符不为'\0'，就进入循环
    {
        count++; //进入一次，count就+1，因为这里传的是abc，所以count会加三次，第四次因为找到的字符是'\0'，就不会进入循环
        str++; //作用是找下一个字符
    }
    return count; //循环结束，count的值为3，而3恰好是该字符串的长度
}

int main()
{
    char arr[] = "abc"; //这个数组中包含的字符为：'a', 'b', 'c', '\0'
    int len = my_strlen(arr); //这里传参是将首字符'a'的地址传给函数
    printf("%d", len);
    return 0;
}

//函数递归法（不使用临时变量）：
#include <stdio.h>
#include <string.h>

int my_strlen(char* str)
{
    if (*str != '\0')
    {
        //首先对字符a的地址解引用，找到字符a，字符a不为'\0'
        //执行return 1 + my_strlen(str+1)
        //开始"递"
        //因为str+1 所以第一次递的参数是b的地址
        //b同理不为\0，再次递，递的是c
        //c同理，再递，递的是\0
        //因为'\0' != '\0'为假，不进入if语句，执行return 0
        //开始"归"
        //最后一层往上归分别是0+1，0+1+1，0+1+1+1，最后将3返回到主函数中的my_strlen，输出结果3
        return 1 + my_strlen(str+1);
    }
    else
    {
        return 0;
    }
}

int main()
{
    char arr[] = "abc";
    int len = my_strlen(arr);
    printf("%d", len);
    return 0;
}


//函数的迭代
//循环就是一种迭代，但迭代不仅限于循环
//以下为实现阶乘的递归和迭代的方法
//递归：
#include <stdio.h>

int Factorial(int x)
{
    if (x <= 1)
        return 1;
    else
        return x * Factorial(x - 1);
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Factorial(n);
    printf("%d", ret);
    return 0;
}

//迭代：
#include <stdio.h>

int Factorial(int x)
{
    int i = 0;
    int ret = 1;
    for(i = 1; i <= x; i++)
    {
        ret *= i;
    }
    return ret;
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Factorial(n);
    printf("%d", ret);
    return 0;
}


//递归和迭代的权衡
//如果用递归写很简单且没有严重的问题（比如重复计算致使效率太低）就使用递归
//反之就考虑迭代的方式